package com.gxc.tree;

public class Trie2 {

    private Trie2[] tries;
    private boolean end;

    public Trie2() {
        tries = new Trie2[26];
    }

    public void insert(String word) {
        Trie2 node = this;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            int n = c - 'a';
            Trie2 trie = node.tries[n];
            if (trie == null) {
                trie = new Trie2();
            }
            node.tries[n] = trie;
            if (i == word.length() - 1) {
                trie.end = true;
            }
            node = trie;
        }
    }

    public boolean search(String word) {
        Trie2 node = this;
        for (int i = 0; i < word.length(); i++) {
            char c = word.charAt(i);
            node = node.tries[c - 'a'];
            if (node == null) return false;
        }
        return node.end;
    }

    public boolean startsWith(String prefix) {
        Trie2 node = this;
        for (int i = 0; i < prefix.length(); i++) {
            char c = prefix.charAt(i);
            node = node.tries[c - 'a'];
            if (node == null) return false;
        }
        return true;
    }
}
